"""
126. 单词接龙 II

按字典wordList 完成从单词 beginWord 到单词 endWord 转化，一个表示此过程的 转换序列 是形式上像 beginWord -> s1 -> s2 -> ... -> sk 这样的单词序列，并满足：

每对相邻的单词之间仅有单个字母不同。
转换过程中的每个单词 si（1 <= i <= k）必须是字典wordList 中的单词。注意，beginWord 不必是字典 wordList 中的单词。
sk == endWord
给你两个单词 beginWord 和 endWord ，以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列 ，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, ..., sk] 的形式返回。



示例 1：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
解释：存在 2 种最短的转换序列：
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"
示例 2：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：[]
解释：endWord "cog" 不在字典 wordList 中，所以不存在符合要求的转换序列。


提示：

1 <= beginWord.length <= 5
endWord.length == beginWord.length
1 <= wordList.length <= 500
wordList[i].length == beginWord.length
beginWord、endWord 和 wordList[i] 由小写英文字母组成
beginWord != endWord
wordList 中的所有单词 互不相同

"""
from collections import deque
from typing import List



class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        if endWord not in wordList:
            return []

        if beginWord in wordList:
            source = wordList.index(beginWord)
        else:
            wordList.append(beginWord)
            source = len(wordList) - 1
        target = wordList.index(endWord)

        n = len(wordList)
        adj = [[] for _ in range(n)]
        for i in range(n - 1):
            for j in range(i + 1, n):
                is_similar = sum(int(c1 != c2) for c1, c2 in zip(wordList[i], wordList[j])) == 1
                if is_similar:
                    adj[i].append(j)
                    adj[j].append(i)

        inf = 9999

        def bfs(s):
            d = [inf] * n
            d[s] = 0
            q = deque([s])
            while q:
                u = q.popleft()
                for v in adj[u]:
                    if d[v] == inf:
                        d[v] = d[u] + 1
                        q.append(v)
            return d

        forward_distance = bfs(source)
        if forward_distance[target] == inf:
            return []
        backward_distance = bfs(target)

        def gather_paths():
            # 有向图路径枚举，采用简化的DFS算法
            paths = []
            stack = []

            def dfs_visit(path, u):
                path.append(u)
                if u == target:
                    paths.append(path.copy())
                else:
                    for v in adj[u]:
                        # if条件是对adj的修饰，相当于是在子图上做dfs
                        if (forward_distance[u] + 1 == forward_distance[v]
                                and forward_distance[v] + backward_distance[v] == forward_distance[target]):
                            dfs_visit(path, v)
                path.pop()

            dfs_visit(stack, source)
            return paths

        paths = gather_paths()

        result = [[wordList[i] for i in p] for p in paths]
        return result


beginWord = "red"
endWord = "tax"
wordList = ["ted", "tex", "red", "tax", "tad", "den", "rex", "pee"]

solution = Solution()
res = solution.findLadders(beginWord, endWord, wordList)
print(res)
